1. Field of the Invention
The present invention relates to a pattern recognition apparatus based on the pattern matching method in which an input image is compared with a multiplicity of predetermined reference patterns.
2. Description of the Prior Art
In pattern recognition, an image read by an image reading apparatus is processed to determine the position, attitude, shape and other such geometric features in the image. Pattern recognition capability is becoming an essential part of the visual systems of intelligent robots able to autonomously adapt and change their behavior to match their surroundings. Pattern recognition has become a subject of central importance in the areas of robotics and computer vision.
Pattern matching is a fundamental technique in the practical implementation of pattern recognition systems. The method consists of comparing an input image pattern with a multiplicity of preset reference patterns and selecting the reference pattern which offers the closest match to the input image. This selection is based on certain evaluation parameters; correlation function and spatial distance are widely used for this.
If f is the input image vector, g.sub.i the ith vector of the reference pattern, * the vector inner product and .parallel..parallel. the vector of the distance in Euclidean space, the correlation function can be defined as EQU (f*g.sub.i)/(.parallel.f.parallel..multidot..parallel.g.sub.i .parallel.).(1)
From this, taking f.sub.j as the vector f element gives EQU .parallel.f.parallel.=(.SIGMA.f.sub.j.sup.2).sup.0.5 ( 2)
In the pattern recognition operation this correlation function is calculated with respect to each of the reference patterns, and the reference pattern producing the maximum value is adopted as the recognition outcome.
Spatial distance is defined by EQU .parallel.f-g.sub.i .parallel. (3)
In this case, too, this space function is calculated with respect to each of the reference patterns and the reference pattern producing the minimum value is adopted as the recognition outcome.
Although correlation and spatial distance can thus be used for the pattern recognition, one problem is that the comparative closeness of the evaluation parameter values and the reference pattern values means that the maximum and minimum values have to be calculated with a high degree of precision and recognition errors can readily occur. Another problem is the large number of quantities which have to be measured using equations (1) to (3) makes it hard to implement the method in hardware.
Pattern matching methods using other evaluation parameters have been proposed, including the one described in "Considerations in the design of character pattern recognition devices" E. C. Greanias & Y. M. Hill, part 4, vol. 5, p. 119 of 1957 IRE National Convention Record. In this method the evaluation parameter (EP) is defined as EQU EP=(area of input image)/average unmatched area of input image and reference pattern) (4)
The denominator in equation (4) is obtained by dividing the total area of the unmatched portions of the input image pattern and the reference pattern by two. Thus, when the input image pattern and reference pattern are very similar, the denominator of equation (4) becomes substantially 0, giving the equation a very large value. Compared to methods using equations (1) or (3), this makes it easier to select the reference pattern and facilitates the recognition operation.
However, there are a number of problems with the pattern recognition method based on equation (4). For example, even when there is a substantial match between an input image pattern and a reference pattern, any positional shift of one pattern relative to the other that leads to an increase in the unmatched area increases the denominator of the equation (4). On the other hand, as the value of the equation (4) numerator is the area of the input image pattern/reference pattern, input image patterns which are either very large or very small give rise to a large variance in the equation (4) values. Another problem is that the decrease in the equation (4) value which accompanies the decrease in the area of the input image pattern produces a convergence of reference pattern values and a reduction in the recognition rate.
When equation (4) is applied to alphanumeric character recognition, the present inventor found that a slight positional shift or deviation of no more than several pixels between an input character pattern and a reference character pattern was enough to produce a major degradation in the recognition rate, making it impractical to use this equation (4) as a basis for the operation of a pattern recognition apparatus.